The concept of k-anonymity, used in the recent literature to formallyevaluate the privacy preservation of published tables, was introduced based onthe notion of quasi-identifiers (or QI for short). The process of obtainingk-anonymity for a given private table is first to recognize the QIs in thetable, and then to anonymize the QI values, the latter being calledk-anonymization. While k-anonymization is usually rigorously validated by theauthors, the definition of QI remains mostly informal, and different authorsseem to have different interpretations of the concept of QI. The purpose ofthis paper is to provide a formal underpinning of QI and examine thecorrectness and incorrectness of various interpretations of QI in our formalframework. We observe that in cases where the concept has been used correctly,its application has been conservative; this note provides a formalunderstanding of the conservative nature in such cases.
展开▼